package model;

import static java.lang.Thread.sleep;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * <p>
 * A java implementation of the Djikstra Algorithm for finding the shortest path
 * in a graph of vertices and edges. Special thanks to Vogella for the guide in
 * implementation</p>
 * <p>
 * The algorithm is executed by calling its execute function with a "From"
 * vertex. This assigns all of the necessary weights to each of the other
 * vertices. To get a shortest path, the getShortestPath method returns a linked
 * list to a second "To" Vertex.</p>
 *
 * @author Dylan Ahmann
 * @author Gregg Roemhildt - Class Programming and JavaDocs
 * @author Sam Brockmann
 * @author Emily Hancock
 * @author Shirin Asadi
 * @date 11/15/13
 * @see http://www.vogella.com/articles/JavaAlgorithmsDijkstra/article.html
 *
 */
public class DjikstraAlgorithm extends Thread {

    private final List<Vertex> vertices;
    private final List<Edge> edges;
    private Set<Vertex> settled;
    private Set<Vertex> unsettled;
    private Map<Vertex, Double> distanceMap;
    private Map<Vertex, Vertex> predecessorsMap;
    private Vertex source;

    /**
     * default constructor
     *
     * @param g graph model
     */
    public DjikstraAlgorithm(Graph g) {
        vertices = new ArrayList<>(g.getVertices());
        edges = new ArrayList<>(g.getEdges());
    }

    /**
     * Step 1 of the two step process. This function executes the algorithm and
     * creates weights on each vertex based on an input vertex.
     *
     */
    public void execute() {
        //set up
        settled = new HashSet<>();
        unsettled = new HashSet<>();
        distanceMap = new HashMap<>();
        predecessorsMap = new HashMap<>();

        for (Vertex v : vertices) {
            distanceMap.put(v, Double.MAX_VALUE);
        }

        distanceMap.put(source, 0.0);
        unsettled.add(source);

        //start main loop
        while (unsettled.size() > 0) {
            Vertex current = getClosest(unsettled);
            setMinimalDistances(current);
//            try {
//                //for demonstration only, this should be removed for production
////                sleep(50);
//            } catch (InterruptedException ex) {
//
//            }
        }
    }

    /**
     * looks for the closest node in the set
     *
     * @param vertices set of vertices
     * @return the shortest distance node
     */
    private Vertex getClosest(Set<Vertex> vertices) {
        Vertex min = null;
        for (Vertex v : vertices) {
            if (min == null) {
                min = v;
            } else if (distanceMap.get(min) > distanceMap.get(v)) {
                min = v;
            }
        }
        return min;
    }

    /**
     * a helper function to search for connecting nodes and add them to be
     * evaluated.
     *
     * @param node Vertex to search from
     */
    private void setMinimalDistances(Vertex node) {
        //list of touching edges
        List<Edge> neighborEdges = node.getEdges();

        //distance of current path
        double currentDistance = distanceMap.get(node);

        for (Edge e : neighborEdges) {
            //for each edge store the neighbor vertex
            Vertex neighbor = e.getNeighbor(node);
            if (!isSettled(neighbor)) {
                if (currentDistance + e.getWeight() < distanceMap.get(neighbor)) {
                    distanceMap.put(neighbor, currentDistance + e.getWeight());
                    predecessorsMap.put(neighbor, node);
                    if (!unsettled.contains(neighbor)) {
                        unsettled.add(neighbor);
                    }
//cool feature for debuggin: neighbor.setName("weight: " + (e.getWeight() + currentDistance));
                }
            }
        }

        unsettled.remove(node);
        settled.add(node);

    }

    /**
     * a helper function to execute()
     *
     * @param v vertex to test
     * @return true if the vertex has been settled, false if not
     */
    private boolean isSettled(Vertex v) {
        return settled.contains(v);
    }

    /**
     * Step 2 of the algorithm returns the route
     *
     * @param target the to vertex in the graph model
     * @return <ul><li>null if no route available</li>
     * <li>linked list of the shortest path from the vertex submitted to the
     * execute function to the vertex submitted to this function</li>
     */
    public LinkedList<Vertex> getShortestPath(Vertex target) {
        if (predecessorsMap == null) {
            return null;
        }
        if (!predecessorsMap.containsKey(target)) {
            return null;
        }
        LinkedList<Vertex> path = new LinkedList<>();
        Vertex current = target;
        while (predecessorsMap.containsKey(current)) {
            path.add(current);
            current = predecessorsMap.get(current);
        }
        path.add(current);
        return path;
    }

    /**
     * run
     *
     * Method to run all the executable functions in sequence from main/listener
     */
    @Override
    public void run() {
        this.execute();
    }

    /**
     * @param source the source to set
     */
    public void setSource(Vertex source) {
        this.source = source;
    }

}
